#include <bits/stdc++.h>
using namespace std;

/*
1353. 最多可以参加的会议数目
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。

请你返回你可以参加的 最大 会议数目。

 

示例 1：



输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。
示例 2：

输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4
 

提示：​​​​​​

1 <= events.length <= 105
events[i].length == 2
1 <= startDayi <= endDayi <= 105
*/

// 法一
class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        // 开始时间 DESC
        sort(events.begin(), events.end());

        // 最小堆 （优先队列)
        priority_queue<int, vector<int>, greater<int>> pq;
        int ans = 0;
        int i = 0, n = events.size();
        int day = 1;
        while (i < n || !pq.empty()) {
            // 当天开始的会议的结束时间 进优先队列
            while (i < n && events[i][0] == day) {
                pq.push(events[i][1]);
                i++;
            }
            // 已经过期的就从队列中pop出来
            while (!pq.empty() && pq.top() < day)   pq.pop();

            // 优先队列非空  那么选择结束时间最早的参加
            if (!pq.empty()) {
                pq.pop();
                ans++;
            }
            day++;
        }
        return ans;
    }
};

// 法二
#include <vector>
#include <algorithm>
#include <numeric>

class Solution {
public:
    int maxEvents(std::vector<std::vector<int>>& events) {
        // 按会议结束时间升序排序，优先处理结束早的会议以最大化参会数量
        std::sort(events.begin(), events.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });

        // 获取最晚的会议结束时间，用于初始化并查集大小
        int mx = events.back()[1];
        // 初始化并查集：fa[x]表示x之后第一个可用时间点
        std::vector<int> fa(mx + 2);  // +2防止越界
        std::iota(fa.begin(), fa.end(), 0);  // 初始时每个时间点的父节点指向自己

        // 查找函数（带路径压缩）
        auto find = [&](auto&& self, int x) -> int {
            if (fa[x] != x) {
                fa[x] = self(self, fa[x]);  // 路径压缩：直接指向根节点
            }
            return fa[x];
        };

        int ans = 0;
        for (const auto& e : events) {
            // 查找当前会议开始时间之后第一个可用时间点
            int x = find(find, e[0]);
            // 如果该时间点在会议时间范围内，则占用该时间点
            if (x <= e[1]) {
                ans++;
                fa[x] = x + 1;  // 标记x已被占用，下次查找时跳过
            }
        }
        return ans;
    }
};